package com.berchen.offer;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
 * 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
 * 2.返回链表中的第一个节点的指针
 * 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
 * 4.你不用输出双向链表，程序会根据你的返回值自动打印输出
 */
public class Test07 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(10);
        TreeNode node6=new TreeNode(6);
        TreeNode node10=new TreeNode(14);
        TreeNode node5=new TreeNode(4);
        TreeNode node7=new TreeNode(8);
        TreeNode node9=new TreeNode(12);
        TreeNode node11=new TreeNode(16);
        node6.left=node5;
        node6.right=node7;
        node10.left=node9;
        node10.right=node11;
        root.left=node6;
        root.right=node10;
        Test07 test07 = new Test07();
        TreeNode convert = test07.Convert(root);
        System.out.println(convert);
    }
    private TreeNode pro; // 保存临时的前一个节点
    private TreeNode root;// 保存链表头
    public TreeNode Convert(TreeNode pRootOfTree) {

        if(pRootOfTree==null){
            return null;
        }
        diGui(pRootOfTree);

        return root;
    }
    public void diGui(TreeNode node){
        if(node==null){
            return;
        }
        diGui(node.left);

        if(pro==null){
            pro=node;
            root=node;
        }else {
            // 前节点的后继节点是当前节点
            pro.right=node;
            // 当前节点的前驱节点指向前节点
            node.left=pro;
            // 当前节点赋值为前节点
            pro=node;
        }
        diGui(node.right);
    }
}
